/*
 * @lc app=leetcode.cn id=888 lang=java
 *
 * [888] 公平的糖果交换
 */

// @lc code=start
class Solution {
    /**
     * 只用返回一个答案
     * 我靠，这个暴力写法居然过了
     * n*2的复杂度诶。
     * @param A
     * @param B
     * @return
     */
    public int[] fairCandySwap(int[] A, int[] B) {
        // int len = Math.max(A.length, B.length);
        // int[] C = new int[len];
        int gap=0;
        int sumA=0,sumB=0;
        for (int i = 0; i < A.length; i++) {
            sumA+=A[i];
        }
        for (int i = 0; i < B.length; i++) {
            sumB+=B[i];
        }
        gap = sumA-sumB;//差值，需要交换差值为它的一半的值的糖果。
        //最后再for循环找
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < B.length; j++) {
                if(A[i]-B[j]==gap/2){
                    return new int[]{A[i],B[j]};
                }
            }
            
        }
        return new int[2];
    }
    /**
     * 较好的方法是排序，避免n*2的复杂度。
     * 我当时以为java自动的排序复杂度也高，没想到效率这么好的么。
     */
    public int[] fairCandySwap1(int[] A, int[] B) {
        int[] ans = new int[2];
        int sumA = 0, sumB = 0;
        for(int i: A){
            sumA += i;
        }
        for(int j: B){
            sumB += j;
        }
        Arrays.sort(A);
        Arrays.sort(B);
        int temp = sumA-(sumA+sumB)/2;
        int i = 0, j = 0;
        while(i<A.length&&j<B.length){
            if(A[i]-B[j]==temp){
                ans[0] = A[i];
                ans[1] = B[j];
                break;
            }
            else if(A[i]-B[j]>temp){
                j++;
            }
            else if(A[i]-B[j]<temp){
                i++;
            }
        }
        return ans;
    }
}
// @lc code=end

